package com.markus.code.图.图1;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/19 17:14
 * todo: 迪杰斯特拉算法：最短路径
 */
public class GraphDijkstra {
    public Map<Node,Integer> dijkstra(Graph graph,Node sourceNode){
        HashMap<Node,Integer> distanceMap = new HashMap<>();
        HashSet<Node> selectNode = new HashSet<>();
        distanceMap.put(sourceNode,0);
        Node minNode = getMinNodeAndUnSelectNode(distanceMap,selectNode);
        while(minNode != null){
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                Integer distance = edge.weight+distanceMap.get(minNode);
                if (!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode,distance);
                }
                Integer sourceDistance = distanceMap.get(toNode);
                if (distance < sourceDistance){
                    distanceMap.put(toNode,distance);
                }
            }
            selectNode.add(minNode);
            minNode = getMinNodeAndUnSelectNode(distanceMap,selectNode);
        }
        return distanceMap;
    }

    private Node getMinNodeAndUnSelectNode(HashMap<Node, Integer> distanceMap,
                                           HashSet<Node> selectNode) {
        Node min = null;
        Integer MinDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            Integer distance = entry.getValue();
            if (MinDistance > distance && !selectNode.contains(node)){
                min = node;
                MinDistance = distance;
            }
        }
        return min;
    }
}
